{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Grover's algorithm examples\n",
    "\n",
    "This notebook has examples demonstrating how to use the Qiskit [Grover](https://qiskit.org/documentation/stubs/qiskit.algorithms.Grover.html) search algorithm, with different oracles."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Finding solutions to 3-SAT problems\n",
    "\n",
    "Let's look at an example 3-Satisfiability (3-SAT) problem and walk-through how we can use Quantum Search to find its satisfying solutions. 3-SAT problems are usually expressed in [Conjunctive Normal Forms (CNF)](https://en.wikipedia.org/wiki/Conjunctive_normal_form) and written in the [DIMACS-CNF](http://www.satcompetition.org/2009/format-benchmarks2009.html) format. For example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "input_3sat_instance = '''\n",
    "c example DIMACS-CNF 3-SAT\n",
    "p cnf 3 5\n",
    "-1 -2 -3 0\n",
    "1 -2 3 0\n",
    "1 2 -3 0\n",
    "1 -2 -3 0\n",
    "-1 2 3 0\n",
    "'''"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The CNF of this 3-SAT instance contains 3 variables and 5 clauses:\n",
    "\n",
    "$(\\neg v_1 \\vee \\neg v_2 \\vee \\neg v_3) \\wedge (v_1 \\vee \\neg v_2 \\vee v_3) \\wedge (v_1 \\vee v_2 \\vee \\neg v_3) \\wedge (v_1 \\vee \\neg v_2 \\vee \\neg v_3) \\wedge (\\neg v_1 \\vee v_2 \\vee v_3)$\n",
    "\n",
    "It can be verified that this 3-SAT problem instance has three satisfying solutions:\n",
    "\n",
    "$(v_1, v_2, v_3) = (T, F, T)$ or $(F, F, F)$ or $(T, T, F)$\n",
    "\n",
    "Or, expressed using the DIMACS notation:\n",
    "\n",
    "`1 -2 3`, or `-1 -2 -3`, or `1 2 -3`.\n",
    "\n",
    "With this example problem input, we then create the corresponding `oracle` for our `Grover` search. In particular, we use the `PhaseOracle` component, which supports parsing DIMACS-CNF format strings and constructing the corresponding oracle circuit."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\"The 'tweedledum' library is required to use 'classical function oracles'. You can install it with 'pip install tweedledum'.\"\n"
     ]
    }
   ],
   "source": [
    "import os\n",
    "import tempfile\n",
    "from qiskit.exceptions import MissingOptionalLibraryError\n",
    "from qiskit.circuit.library.phase_oracle import PhaseOracle\n",
    "\n",
    "\n",
    "fp = tempfile.NamedTemporaryFile(mode='w+t', delete=False)\n",
    "fp.write(input_3sat_instance)\n",
    "file_name = fp.name\n",
    "fp.close()\n",
    "oracle = None\n",
    "try:\n",
    "    oracle = PhaseOracle.from_dimacs_file(file_name)\n",
    "except ImportError as ex:\n",
    "    print(ex)\n",
    "finally:\n",
    "    os.remove(file_name)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `oracle` can now be used to create an Grover instance:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "from qiskit.algorithms import AmplificationProblem\n",
    "\n",
    "problem = None\n",
    "if oracle is not None:\n",
    "    problem = AmplificationProblem(oracle, is_good_state=oracle.evaluate_bitstring)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can then configure the backend and run the Grover instance to get the result:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "from qiskit.algorithms import Grover\n",
    "from qiskit.primitives import Sampler\n",
    "\n",
    "grover = Grover(sampler=Sampler())\n",
    "result = None\n",
    "if problem is not None:\n",
    "    result = grover.amplify(problem)\n",
    "    print(result.assignment)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As seen above, a satisfying solution to the specified 3-SAT problem is obtained. And it is indeed one of the three satisfying solutions.\n",
    "\n",
    "Since we used the `Sampler`, the complete measurement result is also returned, as shown in the plot below, where it can be seen that the binary strings `000`, `011`, and `101` (note the bit order in each string), corresponding to the three satisfying solutions all have high probabilities associated with them."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "from qiskit.tools.visualization import plot_histogram\n",
    "\n",
    "if result is not None:\n",
    "    display(plot_histogram(result.circuit_results[0]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Boolean Logical Expressions\n",
    "\n",
    "Qiskit's `Grover` can also be used to perform Quantum Search on an `Oracle` constructed from other means, in addition to DIMACS. For example, the `PhaseOracle` can actually be configured using arbitrary Boolean logical expressions, as demonstrated below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\"The 'tweedledum' library is required to use 'PhaseOracle'. You can install it with 'pip install tweedledum'.\"\n"
     ]
    }
   ],
   "source": [
    "expression = '(w ^ x) & ~(y ^ z) & (x & y & z)'\n",
    "try:\n",
    "    oracle = PhaseOracle(expression)\n",
    "    problem = AmplificationProblem(oracle, is_good_state=oracle.evaluate_bitstring)\n",
    "    grover = Grover(sampler=Sampler())\n",
    "    result = grover.amplify(problem)\n",
    "    display(plot_histogram(result.circuit_results[0]))\n",
    "except MissingOptionalLibraryError as ex:\n",
    "    print(ex)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the example above, the input Boolean logical expression `'(w ^ x) & ~(y ^ z) & (x & y & z)'` should be quite self-explanatory, where `^`, `~`, and `&` represent the Boolean logical XOR, NOT, and AND operators, respectively. It should be quite easy to figure out the satisfying solution by examining its parts: `w ^ x` calls for `w` and `x` taking different values; `~(y ^ z)` requires `y` and `z` be the same; `x & y & z` dictates all three to be `True`. Putting these together, we get the satisfying solution `(w, x, y, z) = (False, True, True, True)`, which our `Grover`'s result agrees with."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<h3>Version Information</h3><table><tr><th>Qiskit Software</th><th>Version</th></tr><tr><td><code>qiskit-terra</code></td><td>0.23.3</td></tr><tr><td><code>qiskit-aer</code></td><td>0.12.0</td></tr><tr><td><code>qiskit-ibmq-provider</code></td><td>0.20.2</td></tr><tr><td><code>qiskit</code></td><td>0.42.1</td></tr><tr><th>System information</th></tr><tr><td>Python version</td><td>3.10.10</td></tr><tr><td>Python compiler</td><td>GCC 12.2.1 20230201</td></tr><tr><td>Python build</td><td>main, Mar  5 2023 22:26:53</td></tr><tr><td>OS</td><td>Linux</td></tr><tr><td>CPUs</td><td>32</td></tr><tr><td>Memory (Gb)</td><td>125.66083908081055</td></tr><tr><td colspan='2'>Thu May 04 15:38:15 2023 EDT</td></tr></table>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<div style='width: 100%; background-color:#d5d9e0;padding-left: 10px; padding-bottom: 10px; padding-right: 10px; padding-top: 5px'><h3>This code is a part of Qiskit</h3><p>&copy; Copyright IBM 2017, 2023.</p><p>This code is licensed under the Apache License, Version 2.0. You may<br>obtain a copy of this license in the LICENSE.txt file in the root directory<br> of this source tree or at http://www.apache.org/licenses/LICENSE-2.0.<p>Any modifications or derivative works of this code must retain this<br>copyright notice, and modified files need to carry a notice indicating<br>that they have been altered from the originals.</p></div>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import qiskit.tools.jupyter\n",
    "%qiskit_version_table\n",
    "%qiskit_copyright"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.10"
  },
  "vscode": {
   "interpreter": {
    "hash": "4213929014e7aa4f7c83ab6e8b511ecef456337e6cdcd5a9f1a6614ced2a54b2"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
